package br.ufmg.vod.wbr.algorithims.dfs;

import br.ufmg.vod.collections.IntQueueStack;
import br.ufmg.vod.collections.IntStack;
import br.ufmg.vod.wbr.api.Graph;

public class FastDFS implements Runnable, DFS {
	
	public static byte WHITE = DFSData.WHITE;
	public static byte GRAY = DFSData.GRAY;
	public static byte BLACK = DFSData.BLACK;
	
	private DFSData data;
	private IntStack stack;

	public FastDFS(Graph g){
		this.stack = new IntQueueStack(g.getNumVertex());
		this.data = new DFSData(g);
	}
	
	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#run()
	 */
	@Override
	public void run() {
		dfsAllVertex();
	}

	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#dfsAllVertex()
	 */
	public void dfsAllVertex() {
		for (int i = 0; i < this.data.graph.getNumVertex(); i++) {
			dfsSingleVertex(i);
		}
	}

	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#dfsSingleVertex(int)
	 */
	public void dfsSingleVertex(int u) {
		if( this.data.colors[u] == DFSData.WHITE){
			this.data.colors[u] = GRAY;
			this.data.discoveryTime[u] = ++this.data.time;
			this.data.predecessor[u]=u;
			this.data.dist[u]=0;
			
			this.stack.push(u);
			this.stack.push(-1);
			
			this.dfsVisit();
		}
	}

	
	private DFSData dfsVisit() {
		
		while(!stack.isEmpty()){
			recursion:{
				int i = stack.pop()+1; //returns from recursion on last FOR line
				int u = stack.pop();
				
				int[] neighbours = data.graph.getEdges(u); //recover neighbours var
				
				for (; i < neighbours.length; i++) {
					int v = neighbours[i];
					if( v < this.data.graph.getNumVertex() && this.data.colors[v] == WHITE  ){
						this.data.colors[v] = GRAY;
						this.data.discoveryTime[v] = ++this.data.time;
						this.data.predecessor[v]=u;
						this.data.dist[v]=this.data.dist[u]+1;
						
						//RECURSION TIME XD!!!
						stack.push(u);
						stack.push(i);
						stack.push(v);
						stack.push(-1);
						break recursion;
					}
				}
				//RECURSION ENDED
				this.data.colors[u] = BLACK;
				this.data.closeTime[u] = this.data.time;
				this.data.visitedStack.push(u);
			}

		}
		
		return this.data;
		
	}
	
	/* (non-Javadoc)
	 * @see br.ufmg.vod.wbr.algorithims.dfs.DFS#getData()
	 */
	public DFSData getData() {
		return data;
	}
	

	@Override
	public void clear() {
		this.data.clearAllVisitedData();
	}
	

}
